package com.myc.subjects.linkedlist;

import com.myc.subjects.utils.LinkedListUtils;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * Leetcode题号：19
 *
 * 删除链表的倒数第n个节点
 *
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 *
 * 进阶：你能尝试使用一趟扫描实现吗？
 *
 * 示例 1：
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 *
 * 示例 2：
 * 输入：head = [1], n = 1
 * 输出：[]
 *
 * 示例 3：
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 *
 * 提示：
 * 链表中结点的数目为 sz
 * 1 <= sz <= 30
 * 0 <= Node.val <= 100
 * 1 <= n <= sz
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Shanchudaoshudingejiedian {

    public static void main(String[] args) {
        ListNode l5 = new ListNode(4);
        ListNode l4 = new ListNode(3, l5);
        ListNode l3 = new ListNode(2, l4);
        ListNode l2 = new ListNode(1, l3);
        ListNode l1 = new ListNode(0, l2);

        Shanchudaoshudingejiedian shanchudaoshudingejiedian = new Shanchudaoshudingejiedian();
        LinkedListUtils.showLinkedList(shanchudaoshudingejiedian.removeNthFromEnd1(l1, 2));
    }

    /**
     * 方法一：计算长度
     * 时间复杂度：O(n)
     * 先迭代计算出链表长度，再找到倒数第n个节点的上一个节点，使他的next指针指向第n个节点的后面一个节点
     * 注意：这里删除的有可能是头节点，所以需要哨兵节点来辅助一下
     */
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        //定义哨兵节点
        ListNode sentinel = new ListNode(0, head);

        //迭代计算链表的长度
        ListNode curr = head;
        int length = 0;
        while(curr != null){
            curr = curr.next;
            length++;
        }

        //再从头遍历找到第n-1个节点
        curr = sentinel;
        for(int i = 0; i < length - n; i++){
            curr= curr.next;
        }
        curr.next = curr.next.next;//第 n-1 个节点的next指针指向第 n+1 个节点
        return sentinel.next;//返回sentinel.next而不是head，因为head也有可能是被删除的节点
    }

    /**
     * 方法二：使用栈
     * 时间复杂度：O(n)
     * 先将所有节点入栈，再弹栈到倒数第n个节点，此时栈顶元素就是第n-1个元素
     */
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode sentinel = new ListNode(0, head);

        //推荐使用Deque来使用栈的方法
        Deque<ListNode> stack = new ArrayDeque<>();

        //入栈
        ListNode curr = sentinel;
        while(curr != null){
            stack.add(curr);
            curr = curr.next;
        }

        //弹栈
        for(int i = 0; i < n; i++){
            stack.removeLast();
        }

        //栈顶元素即为第n-1个节点
        ListNode target = stack.getLast();
        target.next = target.next.next;
        return sentinel.next;
    }

    /**
     * 方法三：双指针（一次遍历）
     * 时间复杂度：O(n)
     * 定义从头至尾遍历数组的两个指针，两个指针相差n的距离，同时向后遍历，当第一个指针到达最后一个节点时，第二个节点的位置就是第n-1个节点
     */
    public ListNode removeNthFromEnd3(ListNode head, int n) {
        ListNode sentinel = new ListNode(0, head);

        int start = 0;//定义第一个指针
        ListNode startNode = sentinel;//第一个指针对应节点针从哨兵节点开始遍历
        while(start <= n){//第一个先遍历n个节点位置
            startNode = startNode.next;
            start++;
        }

        ListNode endNode = sentinel;//定义第二个指针对应节点针从哨兵节点开始遍历

        //两个指针同时向后遍历直到第一个指针遍历到最后一个节点，此时第二个指针对应的就是倒数第n-1个节点
        while(startNode != null){
            startNode = startNode.next;
            endNode = endNode.next;
        }
        endNode.next = endNode.next.next;
        return sentinel.next;
    }
}

/**
 * 总结：
 * 1.善于利用哨兵节点处理头节点的特殊情况
 * 2.利用双指针解决链表的倒数节点问题
 */
